package org.bookshare.document.navigation.chapters;

import java.util.ArrayList;
import java.util.List;

import org.benetech.collections.IdTree;
import org.benetech.collections.Tree;
import org.benetech.event.EventListener;
import org.benetech.ref.XML;
import org.jdom.Element;

/**
 * A set of chapter candidates. Algorithmically compares the sets on demand, analyzes chapter marker positions, and
 * identifies the same/similar chapters; determines the best chapter set based on accuracy (relative to the other
 * chapter sets) and size (again relative).
 * @author Reuben Firmin
 */
public final class ChapterSets {

	/**
	 * Direction to scan.
	 */
	private enum ScanDirection {
		FORWARD,
		BACKWARD;
	}

	private static final long VERY_LOW_NUMBER = -999999999999999999L;

	// NoCheck MAGIC
	/** The distance, expressed as percentage of the total tree size, that chapters markers can be from each other
	 * to be considered the "same" */
	private static final double PERCENT_DISTANCE = 0.5;
	/** Chapter distance margin of error weighting */
	private static final double MARGIN_OF_ERROR_WEIGHT = 1;
	/** Chapter number distance from average weighting */
	private static final double DISTANCE_FROM_AVERAGE_WEIGHT = 10;
	// CheckOn

	/** Size of all added candidates, so far. */
	private int sumSize;
	/** List of valid candidates. */
	private final List<Chapters> validCandidates = new ArrayList<Chapters>();
	/** Minimum allowed chapters. */
	private int minChapters;
	/** Maximum allowed chapters. */
	private int maxChapters;
	private IdTree<Element, String, String> topOfTree;

	/**
	 * Constructor.
	 * @param minChapters The minimum number of chapters to allow, except for TOC candidates.
	 * @param maxChapters The maximum number of chapters to allow, except for TOC candidates.
	 * @param topOfTree The top of the document
	 */
	public ChapterSets(final int minChapters, final int maxChapters, final IdTree<Element, String, String> topOfTree) {
		this.minChapters = minChapters;
		this.maxChapters = maxChapters;
		this.topOfTree = topOfTree;
	}

	/**
	 * Average size of all candidates.
	 * @return The average size
	 */
	public double avgSize() {
		if (validCandidates.size() > 0) {
			return (double) sumSize / validCandidates.size();
		}
		return 0;
	}

	/**
	 * Add the candidate if it isn't null, and is within chapter size boundaries. Removes chapters that are looking at
	 * pagenum elements.
	 * @param candidate The candidate to add
	 * @param listener The event listener
	 */
	public void addCandidate(final Chapters candidate, final EventListener listener) {
		if (candidate != null) {
			final List<Chapter> chaptersToRemove = new ArrayList<Chapter>();
			for (Chapter chapter : candidate) {
				if (XML.Regex.PAGENUM_PATTERN.matcher(chapter.getElement().getName()).matches()) {
					chaptersToRemove.add(chapter);
				}
				sumSize++;
			}
			for (Chapter chapter : chaptersToRemove) {
				candidate.remove(chapter);
				listener.message("Removing chapter because it's a pagenum");
				sumSize--;
			}
			if (candidate.size() >= minChapters && candidate.size() <= maxChapters) {
				validCandidates.add(candidate);
			} else {
				listener.message(candidate.getDescription() + " is outside valid ranges; will not consider it");
			}
		}
	}

	/**
	 * Find the best set of chapters so far.
	 * @param listener the EventListener
	 * @return null if no candidates offer valid results
	 */
	public Chapters findBest(final EventListener listener)	{
		int bestIndex = -1;
		if (validCandidates.size() > 1) {
			final double[] scores = compareValidCandidates(validCandidates, listener);
			// evaluate the confirm scores vs the index order (i.e. the number of chapters)
			for (int i = 0; i < scores.length; i++) {
				// initial, or score is better than last noted score
				if ((bestIndex < 0 && scores[i] >= VERY_LOW_NUMBER)
						|| (bestIndex >= 0 && scores[i] > scores[bestIndex]))
				{
					bestIndex = i;
				}
			}
		} else if (validCandidates.size() == 1) {
			bestIndex = 0;
		}

		if (bestIndex >= 0) {
			listener.message("Choosing candidate at index: " + bestIndex + ", based on: "
					+ validCandidates.get(bestIndex).getDescription());
			return validCandidates.get(bestIndex);
		} else {
			listener.message("Couldn't auto-detect chapters based on defined strategies.");
			return null;
		}
	}

	/**
	 * Compares valid candidates to find best chapter approximate. This can be run multiple times, but should not
	 * be run in parallel to chapters being added.
	 * @param validCandidates The candidates to compare with each other
	 * @param listener the EventListener
	 * @return scores for each of the candidates
	 */
	private double[] compareValidCandidates(final List<Chapters> validCandidates, final EventListener listener) {
		final double avgValidChapters = (sumSize == 0) ? 0 : (double) sumSize / validCandidates.size();
		listener.message("There are: " + validCandidates.size() + " candidate chapter selections that are valid;"
				+ "average size is: " + avgValidChapters);
		int index = 0;
		listener.message("Calculating distances between chapters.");
		// increment amount for a confirm; max is 1, if the chapter is confirmed in all other candidates
		final double[] scores = new double[validCandidates.size()];
		// The maximum distance, in number of elements, that two chapters can be apart in order to be considered the
		// same. We'll allow up to an PERCENT_DISTANCE variation in chapters, to be considered a "confirm"
		final double maxReasonableDistance = topOfTree.getSize() / (100 / PERCENT_DISTANCE);
		// the amount to increment the confirm score each time we find a chapter. this is set so that the
		// maximum is 1 per chapter across all other candidates. i.e. if the chapter is found in all other
		// candidates, 1 will be added to the confirm score.
		final double incrAmount = (double) 1 / (validCandidates.size() - 1);

		// consider the candidates in order, and evaluate the distance each chapter is from the nearest candidate
		// chapter in other chapter sets
		for (Chapters candidate : validCandidates) {
			candidate.reset();
			for (int chapterIndex = 0; chapterIndex < candidate.size(); chapterIndex++) {
				final Chapter chapter = candidate.get(chapterIndex);
				final double percentThroughCandidate = (double) chapterIndex / candidate.size();
				// set outside range for now; this will be set to the minimum distance in any of the other
				// candidate chapter sets
				chapter.setMinDistance((int) maxReasonableDistance * 2);
				for (Chapters otherCandidate : validCandidates) {
					chapter.setFound(false);
					// if this isn't the same candidate set of chapters
					if (!candidate.equals(otherCandidate)) {
						attemptToFindChapterInOther(percentThroughCandidate, chapter, otherCandidate,
								maxReasonableDistance);
					}
					if (chapter.isFound()) {
						candidate.incrConfirmScore(incrAmount);
					}
				}
				if (chapter.getMinDistance() < maxReasonableDistance) {
					candidate.confirmChapter(chapter);
				}
			}
			scores[index++] = scoreCandidate(listener, candidate, avgValidChapters, maxReasonableDistance);
		}
		return scores;
	}

	/**
	 * Scores the candidate, based on:
	 * 1) the number of chapters confirmed in other candidates (size)
	 * 2) the distance those chapters were from chapters in other candidates (accuracy).
	 * @param listener the EventListener
	 * @param candidate the candidate to score
	 * @param avgValidChapters the average number of chapters across all the sets
	 * @param maxReasonableDistance The maximum distance, in number of elements, that two chapters can be apart in order
	 * to be considered the same. Used to calculate the accuracy.
	 * @return score for the candidate
	 */
	private double scoreCandidate(final EventListener listener, final Chapters candidate, final double avgValidChapters,
			final double maxReasonableDistance)
	{
		double score = -1;
		if (candidate.getNumChaptersConfirmed() > 0) {
			// rating of the accuracy of chapter selection, based on other candidates; bigger is better
			final double chapterAccuracy = candidate.getNumChaptersConfirmed() * (maxReasonableDistance
					- (candidate.getCumulativeDistance() / candidate.getConfirmScore()));
			// rating of the deviance from the average of the number of chapters chosen; smaller is better
			final double numChapterDeviance = maxReasonableDistance * Math.abs(
					candidate.getNumChaptersConfirmed() - avgValidChapters);
			// bigger is better
			score = (MARGIN_OF_ERROR_WEIGHT * chapterAccuracy) - (DISTANCE_FROM_AVERAGE_WEIGHT * numChapterDeviance);
			listener.message("Candidate (" + candidate.getDescription() + ") has a score of " + score
			        + " based on an accuracy " + "weighting of " + chapterAccuracy + " and a size deviance of "
			        + numChapterDeviance + "; confirmed chapters were: " + candidate.getNumChaptersConfirmed()
			        + "; cumulative distance was: " + candidate.getCumulativeDistance() + "; confirm score was "
			        + candidate.getConfirmScore());
		}
		return score;
	}


	/**
	 * Scan the other candidate in both directions, starting from a given percentage through the book, looking for
	 * a chapter that is as close as possible to this chapter, in terms of number of elements distance.
	 * @param percentThroughCandidate Percentage Through Candidate
	 * @param maxReasonableDistance The maximum distance, in number of elements, that two chapters can be apart in order
	 * to be considered the same. Used to calculate the accuracy.
	 * @param chapter current Chapter
	 * @param otherCandidate Other Candidates
	 */
	private void attemptToFindChapterInOther(final double percentThroughCandidate, final Chapter chapter,
			final Chapters otherCandidate, final double maxReasonableDistance)
	{
		final int otherChapterIndex = (int) Math.round(otherCandidate.size() * percentThroughCandidate);
		boolean reachedUpperLimit = false;
		boolean reachedLowerLimit = false;
		// For efficiency, as soon as we find a distance within the reasonable range, we'll stop scanning as long as the
		// next distance doesn't decrease
		for (int offset = 0; !reachedUpperLimit || !reachedLowerLimit; offset++) {
			// look forwards first, if we haven't hit the "limit" (top, or minimum distance scanning up)
			if (!reachedUpperLimit && otherChapterIndex + offset < otherCandidate.size()) {
				reachedUpperLimit = !isWithinRange(ScanDirection.FORWARD, otherCandidate, otherChapterIndex, offset,
						chapter, maxReasonableDistance);
			} else {
				reachedUpperLimit = true;
			}

			// now look backwards.
			// if offset == 0, then no need to do this again, as it'll point to the same node as we
			// just looked at; otherwise the logic is the same as above, but reversed
			if (offset > 0 && !reachedLowerLimit && otherChapterIndex - offset >= 0) {
				reachedLowerLimit = !isWithinRange(ScanDirection.BACKWARD, otherCandidate, otherChapterIndex, offset,
						chapter, maxReasonableDistance);
			} else if (offset > 0) {
				reachedLowerLimit = true;
			}
		}
	}

	/**
	 * Look at the chapter in the given direction, at a offset from the starting (chapter) index in the other chapters
	 * candidate. Compare with the current chapter in terms of distance. Return whether it's within range. If the
	 * distance is less than the closest to the current chapter that we found so far, update the chapter with that
	 * information.
	 * @param scanDirection The direction to scan
	 * @param otherCandidate Other candidate set of chapters
	 * @param otherChapterIndex the current chapter index
	 * @param offset the number of chapters from otherChapterIndex
	 * @param chapter the current chapter
	 * @param maxReasonableDistance The maximum distance, in number of elements, that two chapters can be apart in order
	 * to be considered the same. Used to calculate the accuracy.
	 * @return Whether we're within range.
	 */
	private boolean isWithinRange(final ScanDirection scanDirection, final Chapters otherCandidate,
			final int otherChapterIndex, final int offset, final Chapter chapter, final double maxReasonableDistance)
	{
		boolean limitOutOfRange = false;
		final int direction = scanDirection.equals(ScanDirection.FORWARD) ? 1 : -1;
		final Chapter otherChapter = otherCandidate.get(otherChapterIndex + offset * direction);
		final int distance = chapter.getDistanceFrom(otherChapter);
		// we found two chapters within reasonable range
		if (distance < maxReasonableDistance && distance < chapter.getMinDistance()) {
			chapter.setMinDistance(distance);
			chapter.setFound(true);
		} else if (chapter.isFound()) {
			// we found it, but the distance is no longer within range
			limitOutOfRange = true;
		}
		return !limitOutOfRange;
	}
}


